滑動窗口 (Sliding Window)

解題思路

首先，我們需要理解一個基本概念：如果一個字串是另一個字串的排列，那麼這兩個字串中每個字元出現的次數必須完全相同。

基於這個概念，我們可以使用一種稱為「滑動窗口 (Sliding Window)」的方法來解決這個問題。具體來說，假設我們有兩個字串 s1 和 s2，並且 s1 的長度為 。我們可以在 s2 中遍歷每一個長度為 的子字串，並檢查這個子字串是否與 s1 有相同的字元組成。

為了實現這一點，我們需要使用一種資料結構（例如 hash table）來記錄每個字元的出現次數。當滑動窗口向右移動時，我們只需要重新計算整個窗口的字元計數，並且逐一扣掉 s1 的字元計數。

最後，我們只需檢查 hash table 中所有字元的計數是否為零。如果是，那麼我們就找到了一個符合條件的子字串，也就是說 s1 是 s2 子字串的一種排列。如果不是，我們就繼續移動滑動窗口，直到遍歷完整個 s2。

別閉門造車，一起準備面試吧！
在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！
我們將幫助您撰寫一份出色的履歷表，讓您在眾多求職者中脫穎而出。我們將為您提供專業的建議和指導，幫助您在履歷上呈現最完美的自己。如果心動的話，就別猶豫啦！趕快把握機會，動動手指投遞履歷吧！立即加入 Line 讀書會，和大家一起實現夢想！

履歷諮詢	加入讀書會 (邀請碼：4629)

程式

class Solution {
    fun checkInclusion(s1: String, s2: String): Boolean {
        val s2CharArray = s2.toCharArray()
        for (i in 0..s2.length - s1.length) {
            val table = mutableMapOf<Char, Int>()
            for (j in i until i + s1.length) {
                val char = s2CharArray[j]
                table[char] = (table[char] ?: 0) + 1
            }
            val s1CharArray = s1.toCharArray()
            for (j in s1.indices) {
                val char = s1CharArray[j]
                if (table.containsKey(char)) {
                    table[char] = table[char]!! - 1
                }
            }
            if (table.any { it.value != 0 }) continue
            else return true
        }
        return false
    }
}

複雜度分析

• 時間複雜度:
  ，這裡的 和 分別代表字串 s2 和 s1 的長度。這個時間複雜度表示我們需要在 s2 中遍歷所有長度為 的子字串，並對每個子字串進行操作。由於 s2 的長度為 ，所以我們需要進行 次遍歷。而對每個子字串的操作複雜度為 ，所以總的時間複雜度為 。

• 空間複雜度:
  。這裡的 代表字元集合，也就是所有可能出現的字元。在這道題目中，字元集合是小寫字母，所以 。空間複雜度表示我們需要多少額外的空間來存儲資訊。在這裡，我們需要一個 hash table 來記錄每個字元出現的次數，而 hash table 的大小就是字元集合的大小，所以空間複雜度為 。

　更多演算法題解，一起來學習！

別閉門造車，一起準備面試吧！

在紙上呈現100%完美的你！打爆天下無敵手的履歷怎麼寫？找工作前的第一步：履歷健檢！

履歷諮詢	加入讀書會 (邀請碼：4629)